{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Strange Printer II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPrintable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #奇怪的打印机 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个奇怪的打印机，它有如下两个特殊的打印规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。</li>\n",
    "\t<li>一旦矩形根据上面的规则使用了一种颜色，那么 <strong>相同的颜色不能再被使用&nbsp;</strong>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个初始没有颜色的&nbsp;<code>m x n</code>&nbsp;的矩形&nbsp;<code>targetGrid</code>&nbsp;，其中&nbsp;<code>targetGrid[row][col]</code>&nbsp;是位置&nbsp;<code>(row, col)</code>&nbsp;的颜色。</p>\n",
    "\n",
    "<p>如果你能按照上述规则打印出矩形<em>&nbsp;</em><code>targetGrid</code>&nbsp;，请你返回&nbsp;<code>true</code>&nbsp;，否则返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/19/sample_1_1929.png\" style=\"height: 138px; width: 483px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/19/sample_2_1929.png\" style=\"height: 290px; width: 483px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>targetGrid = [[1,2,1],[2,1,2],[1,2,1]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>没有办法得到 targetGrid ，因为每一轮操作使用的颜色互不相同。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>targetGrid = [[1,1,1],[3,1,3]]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == targetGrid.length</code></li>\n",
    "\t<li><code>n == targetGrid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 60</code></li>\n",
    "\t<li><code>1 &lt;= targetGrid[row][col] &lt;= 60</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [strange-printer-ii](https://leetcode.cn/problems/strange-printer-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [strange-printer-ii](https://leetcode.cn/problems/strange-printer-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]', '[[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]', '[[1,2,1],[2,1,2],[1,2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, mat: List[List[int]]) -> bool:\n",
    "        locs = dict()\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = mat[i][j]\n",
    "                if x not in locs: locs[x] = [i,i,j,j]\n",
    "                else:\n",
    "                    locs[x][0] = min(i,locs[x][0])\n",
    "                    locs[x][1] = max(i,locs[x][1])\n",
    "                    locs[x][2] = min(j,locs[x][2])\n",
    "                    locs[x][3] = max(j,locs[x][3])\n",
    "        g = defaultdict(list)\n",
    "        d = defaultdict(int)\n",
    "        for x,l in locs.items():\n",
    "            for i in range(l[0],l[1]+1):\n",
    "                for j in range(l[2],l[3]+1):\n",
    "                    y = mat[i][j]\n",
    "                    if y == x: continue\n",
    "                    if y in g[x]: continue\n",
    "                    g[x].append(y)\n",
    "                    d[y] += 1\n",
    "        q = list(filter(lambda k:d[k]==0,g.keys()))\n",
    "        res = 0\n",
    "        while q:\n",
    "            res += 1\n",
    "            for y in g[q.pop()]:\n",
    "                d[y] -= 1\n",
    "                if d[y] == 0: q.append(y)\n",
    "        return res == len(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        m,n=len(targetGrid), len(targetGrid[0])\n",
    "        c_mat={i:[m,-1,n,-1] for row in targetGrid for i in row}\n",
    "\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                c=c_mat[targetGrid[row][col]]\n",
    "                if row<c[0]:\n",
    "                    c[0]=row\n",
    "                if row>c[1]:\n",
    "                    c[1]=row\n",
    "                if col<c[2]:\n",
    "                    c[2]=col\n",
    "                if col>c[3]:\n",
    "                    c[3]=col\n",
    "\n",
    "        def is_matrix(c,pos,targetGrid):\n",
    "            for row in range(pos[0],pos[1]+1):\n",
    "                for col in range(pos[2], pos[3]+1):\n",
    "                    t=targetGrid[row][col]\n",
    "                    if t!=0 and t!=c:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        while c_mat:\n",
    "            flag_del_color=False\n",
    "            for c in c_mat:\n",
    "                pos=c_mat[c]\n",
    "                if is_matrix(c,pos,targetGrid):\n",
    "                    for row in range(pos[0],pos[1]+1):\n",
    "                        for col in range(pos[2],pos[3]+1):\n",
    "                            targetGrid[row][col]=0\n",
    "                    c_mat.pop(c)\n",
    "                    flag_del_color=True\n",
    "                    break\n",
    "            if not flag_del_color:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "\n",
    "        def build(c, inds):\n",
    "            x1, y1, x2, y2 = m, n, -1, -1\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if c == targetGrid[i][j]:\n",
    "                        x1, y1 = min(x1, i), min(y1, j)\n",
    "                        x2, y2 = max(x2, i), max(y2, j)\n",
    "            \n",
    "            if x2 == -1: return\n",
    "\n",
    "            visited = [False] * N\n",
    "            for i in range(x1, x2 + 1):\n",
    "                for j in range(y1, y2+1):\n",
    "                    tc = targetGrid[i][j]\n",
    "                    if tc != c and not visited[tc]:\n",
    "                        visited[tc] = True\n",
    "                        inds[tc] += 1\n",
    "                        g[c].append(tc)\n",
    "\n",
    "        N, m, n = 61, len(targetGrid), len(targetGrid[0])\n",
    "        g, inds = [[] for _ in range(N)], [0] * N\n",
    "        \n",
    "        for i in range(0, N):\n",
    "            build(i, inds)\n",
    "        \n",
    "        tot, q = 0, deque([i for i in range(N) if inds[i] == 0])\n",
    "        while q:\n",
    "            c = q.popleft()\n",
    "            tot += 1\n",
    "\n",
    "            for nc in g[c]:\n",
    "                inds[nc] -= 1\n",
    "                if inds[nc] == 0:\n",
    "                    q.append(nc)\n",
    "        \n",
    "        return tot == N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        graph = defaultdict(set)\n",
    "        area = defaultdict(lambda :[inf,inf,-inf,-inf])\n",
    "\n",
    "        m , n = len(targetGrid) , len(targetGrid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                area[targetGrid[i][j]][0] = min(area[targetGrid[i][j]][0],i)\n",
    "                area[targetGrid[i][j]][1] = min(area[targetGrid[i][j]][1],j)\n",
    "                area[targetGrid[i][j]][2] = max(area[targetGrid[i][j]][2],i)\n",
    "                area[targetGrid[i][j]][3] = max(area[targetGrid[i][j]][3],j)\n",
    "\n",
    "        indeg = defaultdict(int)\n",
    "        for k , (min_h,min_w,max_h,max_w) in area.items():\n",
    "            for i in range(min_h,max_h+1):\n",
    "                for j in range(min_w,max_w+1):\n",
    "                    if targetGrid[i][j] != k and targetGrid[i][j] not in graph[k]:\n",
    "                        if k in graph[targetGrid[i][j]]:return False\n",
    "                        graph[k].add(targetGrid[i][j])\n",
    "                        indeg[targetGrid[i][j]] += 1\n",
    "        \n",
    "        queue = deque([k for k in area if indeg[k] == 0])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for nxt in graph[node]:\n",
    "                indeg[nxt] -= 1\n",
    "                if indeg[nxt] == 0:\n",
    "                    queue.append(nxt)\n",
    "        \n",
    "        return all([indeg[k] == 0 for k in area])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        m, n = len(targetGrid), len(targetGrid[0])\n",
    "        graph = collections.defaultdict(list)\n",
    "        ind = collections.Counter()\n",
    "        def dfs(color):\n",
    "            left, right, up, down = n, - 1, m, - 1\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if targetGrid[i][j] == color:\n",
    "                        left = min(left, j)\n",
    "                        right = max(right, j)\n",
    "                        up = min(up, i)\n",
    "                        down = max(down, i)\n",
    "            visit = set([color])\n",
    "            for i in range(up, down + 1):\n",
    "                for j in range(left, right + 1):\n",
    "                    if targetGrid[i][j] not in visit:\n",
    "                        visit.add(targetGrid[i][j])\n",
    "                        graph[color].append(targetGrid[i][j])\n",
    "                        ind[targetGrid[i][j]] += 1 \n",
    "        for i in range(1, 61):\n",
    "            dfs(i)\n",
    "        \n",
    "        queue = collections.deque([i for i in range(1, 61) if i not in ind])\n",
    "        cnt = 0\n",
    "        while queue:\n",
    "            c = queue.popleft()\n",
    "            cnt += 1 \n",
    "            for nei in graph[c]:\n",
    "                ind[nei] -= 1 \n",
    "                if ind[nei] == 0:\n",
    "                    queue.append(nei)\n",
    "        return cnt == 60"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        m=len(targetGrid)\n",
    "        n=len(targetGrid[0])\n",
    "        dic=collections.defaultdict(lambda: [inf,-inf,inf,-inf])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c=targetGrid[i][j]\n",
    "                dic[c][0]=min(dic[c][0],i)\n",
    "                dic[c][1]=max(dic[c][1],i)\n",
    "                dic[c][2]=min(dic[c][2],j)\n",
    "                dic[c][3]=max(dic[c][3],j)\n",
    "        mx=max(dic)\n",
    "        ad=collections.defaultdict(list)\n",
    "        ind=collections.defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c=targetGrid[i][j]\n",
    "                for k in dic:\n",
    "                    if k==c:\n",
    "                        continue\n",
    "                    d=dic[k][0]\n",
    "                    u=dic[k][1]\n",
    "                    l=dic[k][2]\n",
    "                    r=dic[k][3]\n",
    "                  #  print(i,j,d,u,l,r)\n",
    "                    if d<=i<=u and l<=j<=r:\n",
    "                        if c not in ad[k]:\n",
    "                            ad[k].append(c)\n",
    "                            ind[c]+=1\n",
    "        stack=[]\n",
    "       # print(ind)\n",
    "       # print(ad)\n",
    "        for i in range(1,mx+1):\n",
    "            if ind[i]==0:\n",
    "                stack.append(i)\n",
    "        #print(stack)\n",
    "        while stack:\n",
    "            cur=stack.pop(0)\n",
    "            for nex in ad[cur]:\n",
    "                ind[nex]-=1\n",
    "                if ind[nex]==0:\n",
    "                    stack.append(nex)\n",
    "      #  print(ind)\n",
    "       \n",
    "        if sum(ind.values())==0 :\n",
    "            return True\n",
    "        return False\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        m, n = len(targetGrid), len(targetGrid[0])\n",
    "        # decide bounding box\n",
    "        max_row, min_row = {}, {}\n",
    "        max_col, min_col = {}, {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                color = targetGrid[i][j]\n",
    "                max_row[color] = max(max_row.get(color, -1), i)\n",
    "                min_row[color] = min(min_row.get(color, float(\"inf\")), i)\n",
    "\n",
    "                max_col[color] = max(max_col.get(color, -1), j)\n",
    "                min_col[color] = min(min_col.get(color, float(\"inf\")), j)\n",
    "        # try to remove\n",
    "        while True:\n",
    "            any_remove = False\n",
    "            any_exist = False\n",
    "            for c in range(1, 61):\n",
    "                if max_row.get(c, -1) == -1:\n",
    "                    continue\n",
    "                can_remove = True\n",
    "                any_exist = True\n",
    "                # print(f\"checking bounding box for: {c} @ ({min_row[c]}, {min_col[c]}) -> ({max_row[c]}, {max_col[c]})\")\n",
    "                for i in range(min_row[c], max_row[c] + 1):\n",
    "                    for j in range(min_col[c], max_col[c] + 1):\n",
    "                        if targetGrid[i][j] != 0 and targetGrid[i][j] != c:\n",
    "                            can_remove = False\n",
    "                            break\n",
    "                if can_remove:\n",
    "                    # print(f\"remove: {c}\")\n",
    "                    any_remove = True\n",
    "                    for i in range(min_row[c], max_row[c] + 1):\n",
    "                        for j in range(min_col[c], max_col[c] + 1):\n",
    "                            targetGrid[i][j] = 0\n",
    "                    # 记得要删除这个颜色\n",
    "                    max_row[c] = -1\n",
    "            if not any_exist:\n",
    "                # 颜色全部删除了，正确\n",
    "                return True\n",
    "            # 颜色没有全部删除，但是无法删除\n",
    "            if not any_remove:\n",
    "                return False\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        m, n = len(targetGrid), len(targetGrid[0])\n",
    "        mx = max(max(r) for r in targetGrid)\n",
    "        cmp = [[0] * (mx + 1) for _ in range(mx +1)]\n",
    "        dq = defaultdict(lambda: [inf, -inf, inf, -inf])\n",
    "        colors = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a, b, c, d = dq[targetGrid[i][j]]\n",
    "                a = min(a, j)\n",
    "                b = max(b, j)\n",
    "                c = min(c, i)\n",
    "                d = max(d, i)\n",
    "                dq[targetGrid[i][j]] = a, b, c, d\n",
    "                colors.add(targetGrid[i][j])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tmp = targetGrid[i][j]\n",
    "                for color in colors:\n",
    "                    if color != tmp:\n",
    "                        a, b, c, d = dq[color]\n",
    "                        if a <= j <= b and c <= i <= d:\n",
    "                            if cmp[color][tmp] == 1:\n",
    "                                return False\n",
    "                            else:\n",
    "                                cmp[color][tmp] = -1\n",
    "                                cmp[tmp][color] = 1\n",
    "        \n",
    "        g = [[] for _ in range(mx + 1)]\n",
    "        deg_in = [0] * (mx + 1)\n",
    "        sorted_colors = sorted(colors)\n",
    "        for i in range(len(sorted_colors) - 1):\n",
    "            for j in range(i + 1, len(sorted_colors)):\n",
    "                if cmp[sorted_colors[i]][sorted_colors[j]] == 1:\n",
    "                    g[sorted_colors[j]].append(sorted_colors[i])\n",
    "                    deg_in[sorted_colors[i]] += 1\n",
    "                elif cmp[sorted_colors[i]][sorted_colors[j]] == -1:\n",
    "                    g[sorted_colors[i]].append(sorted_colors[j])\n",
    "                    deg_in[sorted_colors[j]] += 1\n",
    "        start = [color for color in sorted_colors if deg_in[color] == 0]\n",
    "        if not start: return False\n",
    "        ans = True \n",
    "\n",
    "        def dfs(node, path):\n",
    "            nonlocal ans \n",
    "            if ans:\n",
    "                for nei in g[node]:\n",
    "                    if nei in path:\n",
    "                        ans = False\n",
    "                        return \n",
    "                    else:\n",
    "                        dfs(nei, path | {nei})\n",
    "\n",
    "        for i in start:\n",
    "            if not ans: return ans \n",
    "            dfs(i, {i})\n",
    "        \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        m=len(targetGrid)\n",
    "        n=len(targetGrid[0])\n",
    "        dic=collections.defaultdict(lambda: [inf,-inf,inf,-inf])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c=targetGrid[i][j]\n",
    "                dic[c][0]=min(dic[c][0],i)\n",
    "                dic[c][1]=max(dic[c][1],i)\n",
    "                dic[c][2]=min(dic[c][2],j)\n",
    "                dic[c][3]=max(dic[c][3],j)\n",
    "        mx=max(dic)\n",
    "        ad=collections.defaultdict(list)\n",
    "        ind=collections.defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c=targetGrid[i][j]\n",
    "                for k in dic:\n",
    "                    if k==c:\n",
    "                        continue\n",
    "                    d=dic[k][0]\n",
    "                    u=dic[k][1]\n",
    "                    l=dic[k][2]\n",
    "                    r=dic[k][3]\n",
    "                  #  print(i,j,d,u,l,r)\n",
    "                    if d<=i<=u and l<=j<=r:\n",
    "                        if c not in ad[k]:\n",
    "                            ad[k].append(c)\n",
    "                            ind[c]+=1\n",
    "        stack=[]\n",
    "        print(ind)\n",
    "        print(ad)\n",
    "        for i in range(1,mx+1):\n",
    "            if ind[i]==0:\n",
    "                stack.append(i)\n",
    "        print(stack)\n",
    "        while stack:\n",
    "            cur=stack.pop(0)\n",
    "            for nex in ad[cur]:\n",
    "                ind[nex]-=1\n",
    "                if ind[nex]==0:\n",
    "                    stack.append(nex)\n",
    "        print(ind)\n",
    "       \n",
    "        if sum(ind.values())==0 :\n",
    "            return True\n",
    "        return False\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        e=collections.defaultdict(list)\n",
    "        ind=collections.Counter()\n",
    "        xx,yy=collections.defaultdict(list),collections.defaultdict(list)\n",
    "        m,n=len(targetGrid),len(targetGrid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                xx[targetGrid[i][j]].append(i)\n",
    "                yy[targetGrid[i][j]].append(j)\n",
    "        \n",
    "        ls=list(xx.keys())\n",
    "        #print(ls,xx,yy)\n",
    "        for key in ls:\n",
    "            xx[key].sort()\n",
    "            yy[key].sort()\n",
    "            fx,fy,tx,ty=xx[key][0],yy[key][0],xx[key][-1],yy[key][-1]\n",
    "            #print(key,fx,fy,tx,ty)\n",
    "            s=set()\n",
    "            for i in range(fx,tx+1):\n",
    "                for j in range(fy,ty+1):\n",
    "                    if targetGrid[i][j]!=key:\n",
    "                        s.add(targetGrid[i][j])\n",
    "            for k in list(s):\n",
    "                e[key].append(k)\n",
    "                ind[k]+=1\n",
    "        #print(e,ind)\n",
    "        q=[]\n",
    "        for key in ls:\n",
    "            if ind[key]==0:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            tp=q.pop()\n",
    "            for i in e[tp]:\n",
    "                ind[i]-=1\n",
    "                if ind[i]==0:\n",
    "                    q.append(i)\n",
    "        for key in ls:\n",
    "            if ind[key]>0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from graphlib import TopologicalSorter, CycleError\r\n",
    "class Solution:\r\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\r\n",
    "        # color -> [ul_i, ul_j, lr_i, lr_j]\r\n",
    "        rectangles: dict[int, list[int]] = dict()\r\n",
    "        m = len(targetGrid)\r\n",
    "        n = len(targetGrid[0])\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if targetGrid[i][j] not in rectangles:\r\n",
    "                    rectangles[targetGrid[i][j]] = [m - 1, n - 1, 0, 0]\r\n",
    "                rectangles[targetGrid[i][j]][0] = min(rectangles[targetGrid[i][j]][0], i)\r\n",
    "                rectangles[targetGrid[i][j]][1] = min(rectangles[targetGrid[i][j]][1], j)\r\n",
    "                rectangles[targetGrid[i][j]][2] = max(rectangles[targetGrid[i][j]][2], i)\r\n",
    "                rectangles[targetGrid[i][j]][3] = max(rectangles[targetGrid[i][j]][3], j)\r\n",
    "        \r\n",
    "        # any other color b appear within a rectangle area of some color a\r\n",
    "        # were printed after a\r\n",
    "        graph: dict[int, set[int]] = {c: set() for c in rectangles.keys()}\r\n",
    "        for c, (ui, uj, li, lj) in rectangles.items():\r\n",
    "            for i in range(ui, li + 1):\r\n",
    "                for j in range(uj, lj + 1):\r\n",
    "                    if targetGrid[i][j] != c:\r\n",
    "                        graph[targetGrid[i][j]].add(c)\r\n",
    "        \r\n",
    "        try:\r\n",
    "            TopologicalSorter(graph).prepare()\r\n",
    "        except CycleError:\r\n",
    "            return False\r\n",
    "        \r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        g = targetGrid\n",
    "        m, n = len(g), len(g[0])\n",
    "        mp = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mp[g[i][j]].append((i,j))\n",
    "        # deg = [0] * len(mp)\n",
    "        deg = defaultdict(int)\n",
    "        rg = defaultdict(list)\n",
    "        for color in mp:\n",
    "            x1, y1 = inf, inf\n",
    "            x2, y2 = -inf, -inf\n",
    "            for x, y in mp[color]:\n",
    "                x1, y1 = min(x, x1), min(y, y1)\n",
    "                x2, y2 = max(x, x2), max(y, y2)\n",
    "            for nc in mp:\n",
    "                if nc != color:\n",
    "                    for x, y in mp[nc]:\n",
    "                        if x1 <= x <= x2 and y1 <= y <= y2:\n",
    "                            deg[color] += 1\n",
    "                            rg[nc].append(color)\n",
    "                            break\n",
    "        # 1 2 3\n",
    "        # 3 2 1\n",
    "        # print(f'{deg},{rg}')\n",
    "        q = deque([color for color in mp if color not in deg])\n",
    "        # print(f'{q}')\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            color = q.popleft()\n",
    "            cnt += 1\n",
    "            for y in rg[color]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return len(mp) == cnt\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "\n",
    "        m, n = len(targetGrid), len(targetGrid[0])\n",
    "        color = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                color[targetGrid[i][j]].append([i, j])\n",
    "\n",
    "        dct = defaultdict(list)\n",
    "        degree = defaultdict(int)\n",
    "        for c1 in color:\n",
    "            x1, x2 = min(ls[0] for ls in color[c1]), max(ls[0] for ls in color[c1])\n",
    "            y1, y2 = min(ls[1] for ls in color[c1]), max(ls[1] for ls in color[c1])\n",
    "            for c2 in color:\n",
    "                if c2 != c1:\n",
    "                    for x, y in color[c2]:\n",
    "                        if x1 <= x <= x2 and y1 <= y <= y2:\n",
    "                            dct[c1].append(c2)\n",
    "                            degree[c2] += 1\n",
    "                            break\n",
    "\n",
    "        cover = 0\n",
    "        stack = [c for c in color if not degree[c]]\n",
    "        while stack:\n",
    "            cover += len(stack)\n",
    "            nex = []\n",
    "            for c in stack:\n",
    "                for r in dct[c]:\n",
    "                    degree[r] -= 1\n",
    "                    if not degree[r]:\n",
    "                        nex.append(r)\n",
    "            stack = nex\n",
    "        return cover == len(color)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        minr, maxr = defaultdict(lambda: inf), defaultdict(int)\n",
    "        minc, maxc = defaultdict(lambda: inf), defaultdict(int)\n",
    "        s = set()\n",
    "        m, n = len(targetGrid), len(targetGrid[0])\n",
    "        mp = defaultdict(list)\n",
    "        mc = defaultdict(int)\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            num = targetGrid[i][j]\n",
    "            minr[num] = min(minr[num], i)\n",
    "            maxr[num] = max(maxr[num], i)\n",
    "            minc[num] = min(minc[num], j)\n",
    "            maxc[num] = max(maxc[num], j)\n",
    "            s.add(num)\n",
    "\n",
    "        for num in s:\n",
    "            for i in range(minr[num], maxr[num] + 1):\n",
    "                for j in range(minc[num], maxc[num] + 1):\n",
    "                    if targetGrid[i][j] != num:\n",
    "                        mp[num].append(targetGrid[i][j])\n",
    "                        mc[targetGrid[i][j]] += 1\n",
    "        q = deque()\n",
    "        for num in s:\n",
    "            if mc[num] == 0:\n",
    "                q.append(num)\n",
    "        \n",
    "        while q:\n",
    "            num = q.popleft()\n",
    "            for np in mp[num]:\n",
    "                mc[np] -= 1\n",
    "                if mc[np] == 0:\n",
    "                    q.append(np)\n",
    "        \n",
    "        for num in s:\n",
    "            if mc[num] > 0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        m, n = len(targetGrid), len(targetGrid[0])\n",
    "        color = defaultdict(list) \n",
    "        areas = defaultdict(tuple)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                color[targetGrid[i][j]].append((i,j))\n",
    "        for c, vec in color.items():\n",
    "            x1,x2 = float('inf'), 0\n",
    "            y1,y2 = float('inf'), 0 \n",
    "            for (x, y) in vec:\n",
    "                x1 = min(x1, x) \n",
    "                x2 = max(x2, x)\n",
    "                y1 = min(y1, y) \n",
    "                y2 = max(y2, y) \n",
    "            areas[c] = (x1, y1, x2, y2)\n",
    "        g = defaultdict(list) \n",
    "        indeg = defaultdict(int) \n",
    "        for c in areas:\n",
    "            x1,y1,x2,y2 = areas[c]\n",
    "            for x in range(x1,x2+1):\n",
    "                for y in range(y1,y2+1):\n",
    "                    if targetGrid[x][y] != c:\n",
    "                        g[c].append(targetGrid[x][y]) \n",
    "                        indeg[targetGrid[x][y]] += 1\n",
    "        blank = [[0] * n for _ in range(m)]\n",
    "        Q = deque() \n",
    "        for c in areas:\n",
    "            if indeg[c] == 0:\n",
    "                Q.append(c) \n",
    "        while Q:\n",
    "            u = Q.popleft() \n",
    "            x1,y1,x2,y2 = areas[u]\n",
    "            for x in range(x1,x2+1):\n",
    "                for y in range(y1,y2+1):\n",
    "                    blank[x][y] = u \n",
    "            for v in g[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    Q.append(v) \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if blank[i][j] != targetGrid[i][j]:\n",
    "                    return False \n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        \n",
    "        color = defaultdict(list)\n",
    "        m, n = len(targetGrid), len(targetGrid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                color[targetGrid[i][j]].append([i, j])\n",
    "        \n",
    "        pos = defaultdict(list)\n",
    "        for c in color:\n",
    "            lst = color[c]\n",
    "            x1 = min(x for x, _ in lst)\n",
    "            x2 = max(x for x, _ in lst)\n",
    "\n",
    "            y1 = min(x for _, x in lst)\n",
    "            y2 = max(x for _, x in lst)\n",
    "            pos[c] = [x1, x2, y1, y2]\n",
    "        \n",
    "        nodes = list(pos.keys())\n",
    "        degree = defaultdict(int)\n",
    "        dct = defaultdict(list)\n",
    "        m = len(nodes)\n",
    "        for x in nodes:\n",
    "            a1, a2, b1, b2 = pos[x]\n",
    "            for y in nodes:\n",
    "                if x != y:\n",
    "                    for a, b in color[y]:\n",
    "                        if a1<=a<=a2 and b1<=b<=b2:\n",
    "                            dct[x].append(y)\n",
    "                            degree[y] += 1\n",
    "        stack = [x for x in nodes if not degree[x]]\n",
    "        while stack:\n",
    "            nex=  []\n",
    "            for i in stack:\n",
    "                for j in dct[i]:\n",
    "                    degree[j] -= 1\n",
    "                    if not degree[j]:\n",
    "                        nex.append(j)\n",
    "            stack = nex[:]\n",
    "        return all(degree[x]==0 for x in nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\n",
    "        xref = defaultdict(lambda :[inf, -inf])\n",
    "        yref = defaultdict(lambda :[inf, -inf])\n",
    "        m, n = len(targetGrid), len(targetGrid[0])\n",
    "        ref = defaultdict(set)\n",
    "        res = defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                v = targetGrid[i][j]\n",
    "                res[v] += 1\n",
    "                xref[v][0] = min(xref[v][0], i)\n",
    "                xref[v][1] = max(xref[v][1], i)\n",
    "                yref[v][0] = min(yref[v][0], j)\n",
    "                yref[v][1] = max(yref[v][1], j)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for r in xref:\n",
    "                    if xref[r][0] <= i <= xref[r][1] and yref[r][0] <= j <= yref[r][1]:\n",
    "                        ref[(i, j)].add(r)\n",
    "        target = defaultdict(int)\n",
    "        for i in xref:\n",
    "            target[i] = (xref[i][1] - xref[i][0] + 1) * (yref[i][1] - yref[i][0] + 1)\n",
    "        que = deque()\n",
    "        for i in res:\n",
    "            if res[i] == target[i]:\n",
    "                que.append(i)\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            for i in range(xref[cur][0], xref[cur][1] + 1):\n",
    "                for j in range(yref[cur][0], yref[cur][1] + 1):\n",
    "                    if targetGrid[i][j] == cur:\n",
    "                        targetGrid[i][j] = 0\n",
    "                        for r in ref[(i, j)]:\n",
    "                            res[r] += 1\n",
    "                            if res[r] == target[r]:\n",
    "                                que.append(r)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if targetGrid[i][j]:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isPrintable(self, targetGrid: List[List[int]]) -> bool:\r\n",
    "        colors = collections.defaultdict(set) # 【同种颜色格子坐标集合】\r\n",
    "        for r,row in enumerate(targetGrid):\r\n",
    "            for c,pt in enumerate(row):\r\n",
    "                colors[pt].add((r,c))\r\n",
    "\r\n",
    "        scale = {p : [\r\n",
    "                        min(r for r,c in colors[p]),\r\n",
    "                        min(c for r,c in colors[p]),\r\n",
    "                        max(r for r,c in colors[p]),\r\n",
    "                        max(c for r,c in colors[p])]\r\n",
    "                    for p in colors\r\n",
    "                }       # 【覆盖某颜色所需的最小矩形】\r\n",
    "        \r\n",
    "        unfilled = {p: set( \r\n",
    "                        (r,c)\r\n",
    "                        for r in range(scale[p][0],scale[p][2]+1)\r\n",
    "                        for c in range(scale[p][1],scale[p][3]+1)\r\n",
    "                        if targetGrid[r][c]!=p\r\n",
    "                        )\r\n",
    "                   for p in colors\r\n",
    "                }       #【某颜色的最小矩形中，不是该颜色的格子坐标集合】\r\n",
    "\r\n",
    "        while(unfilled):\r\n",
    "            for p in unfilled:\r\n",
    "                if not unfilled[p]: # 选取一个可以上色的颜色；\r\n",
    "                    break\r\n",
    "            else:\r\n",
    "                return False        # 如果没有，则说明没有合适的方案，返回false；\r\n",
    "            unfilled.pop(p)\r\n",
    "            for q in unfilled:\r\n",
    "                unfilled[q]-=colors[p] # 上色的过程，去掉其他所有元素的unfilled \r\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
